package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.Stack;

public class GetKthFromEnd22 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //处理特殊情况
        if(head==null || k<=0){
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        while (head!=null){
            stack.push(head);
            head = head.next;
        }
        //剪枝
        if(stack.size()<k){
            return null;
        }
        while(k>0){
            if(k==1){
                return stack.pop();
            }
            stack.pop();
            k--;
        }
        return null;
    }
    //思路：先走链表和后走链表
    public ListNode getKthFromEnd1(ListNode head, int k) {
        //定义先走链表和后走链表
        ListNode former = head, latter = head;
        //先走链表走k步
        for(int i = 0; i<k;i++){
            former = former.next;
        }
        //先走链表和后走链表指针一起走，直到先走指针为null
        while (former!=null){
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }

}
